package leecode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        //1.两数之和
//        int[] arr = {2,7,11,15};
//        System.out.println(Arrays.toString(twoSum(arr, 9)));

        //2.回文数
//        System.out.println(123/1000);
//        System.out.println(121%100/10);
//        isPalindrome(12321);

        //罗马转数字
//        System.out.println(romanToInt("III"));

        //最长公共前缀
        String[] strs1 = {"fower","flow","tlght"};
        String[] strs2 = {"dog","racecar","car"};
        System.out.println(longestCommonPrefix(strs1));
    }

    public static int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                return new int[]{i, map.get(target - nums[i])};
            }
            map.put(nums[i], i);
        }
        throw new RuntimeException("no matched numbers");
    }

    /**
     * 回文数数学解法
     * @param x
     * @return
     */
    public static boolean isPalindrome(int x) {
            if (x < 0) {
                return false;
            }
            int div = 1;
            //获取x的最高多少十进制位
            while (x / div > 10) {
                div *= 10;
            }
            //循环 获得最高位和最低位进行比较
            while (x > 0) {
                int left = x / div;//得到最高位
                int right = x % 10;//得到最低位
                if (left != right) return false;
                /**
                 * 获取去掉最高和最低位的整数，以及它的最高十进制位，进入下一轮比较
                 */
                x = x % div;//去掉最高位
                x = x / 10;//去掉最低位
                div = div / 100;//减去两个十进制位，得到最高十进制位
            }
            return true;
    }

    public static int romanToInt(String s) {
        Map<Character, Integer> R = new HashMap<>();
        R.put('I', 1);
        R.put('V', 5);
        R.put('X', 10);
        R.put('L', 50);
        R.put('C', 100);
        R.put('D', 500);
        R.put('M', 1000);
        char[] arr = s.toCharArray();
        if(arr.length < 2) {
            return R.get(arr[0]);
        }
        int sum = 0;
        int a = 0;
        for (int i = 1; i < arr.length; i++) {//从第一个累加到倒数第二个数字
            int left = R.get(arr[i-1]);
            int right = R.get(arr[i]);
            //按照规则，只要左边的数比右边小，那左边的数就取负数。
            a = left < right ? 0 - left : left;
            sum += a;
        }
        return sum + R.get(arr[arr.length-1]);//加上最后一个
    }

    public static String longestCommonPrefix(String[] strs) {
        //从左到右比较 获得公共前缀
        if (strs.length < 1 || strs == null) {
            return "";
        }
        if (strs.length == 1) {
            return strs[0];
        }

        String left = strs[0];
        String prefix = left;
        for (int i = 1; i < strs.length; i++) {
            prefix = longestCommonPrefix(prefix, strs[i]);
            if (prefix.equals("")) break;
        }
        return prefix;
    }

    private static String longestCommonPrefix(String prefix, String str) {
        int length = Math.min(prefix.length(), str.length());
        int i = 0;
        String comm = "";
        while (i < length) {
            //charAt函数
            if (prefix.charAt(i) != str.charAt(i)) {
                break;
            }
            comm = prefix.substring(0, i+1);
            i++;
        }
        return comm;
    }
}
